Journal
Scientific and Technical Journal of Information Technologies, Mechanics and Optics
UDK004.421.2:519.17004.657
Issue:2 (148)
Multiple context-free path querying by matrix multiplication
Annotation
Many graph analysis problems can be formulated as formal language-constrained path querying problems where the formal languages are used as constraints for navigational path queries. Recently, the context-free language (CFL) reachability formulation has become very popular and can be used in many areas, for example, querying graph databases, Resource Description Framework (RDF) analysis. However, the generative capacity of context-free grammars (CFGs) is too weak to generate some complex queries, for example, from natural languages, and the various extensions of CFGs have been proposed. Multiple context-free grammar (MCFG) is one of such extensions of CFGs. Despite the fact that, to the best of our knowledge, there is no algorithm for MCFL-reachability, this problem is known to be decidable. This paper is devoted to developing the first such algorithm for the MCFL-reachability problem. The essence of the proposed algorithm is to use a set of Boolean matrices and operations on them to find paths in a graph that satisfy the given constraints. The main operation here is Boolean matrix multiplication. As a result, the algorithm returns a set of matrices containing all information needed to solve the MCFL-reachability problem. The presented algorithm is implemented in Python using GraphBLAS API. An analysis of real RDF data and synthetic graphs for some MCFLs is performed. The study showed that using a sparse format for matrix storage and parallel computing for graphs with tens of thousands of edges the analysis time can be 10–20 minutes. The result of the analysis provides tens of millions of reachable vertex pairs. The proposed algorithm can be applied in problems of static code analysis, bioinformatics, network analysis, as well as in graph databases when a path query cannot be expressed using context-free grammars. The provided algorithm is linear algebra-based, hence, it allows one to use high-performance libraries and utilize modern parallel hardware.
Keywords
Постоянный URL
Articles in current issue
- Polymer composition with phenanthrenequinone for recording relief holographic gratings
- Modern approaches to the application of mathematical modeling methods in biomedical research
- Analysis of the phase images obtained during the collection of a holographic registration system based on the geometric phase effect and a polarization camera
- Color triangle color separation system for colorimetric research in microscopy
- The concept of aerial photography using a two-element active optoelectronic complex
- Variational problem of adaptive optimal control. Theoretical and applied computer analysis
- Brief review of the development of theories of robustness, roughness and bifurcations of dynamic systems
- Predicting the results of the 16-factor R. Cattell test based on the analysis of text posts of social network users
- Methodology for the control of electric power distribution system components to ensure the quality of consumed electricity
- Voice based answer evaluation system for physically disabled students using natural language processing and machine learning
- Natural language based malicious domain detection using machine learning and deep learning
- Hybrid JAYA algorithm for workflow scheduling in cloud
- Information model of the essential goods purchase duration
- Analysis and control of user engagement in personalized mobile assisting software for chronic disease patients
- Role discovery in node-attributed public transportation networks: the model description
- A survey of network intrusion detection systems based deep learning approaches
- Monitoring the health status of the population by age groups
- An intelligent shell game optimization based energy consumption analytics model for smart metering data
- Active voltage damping method with negative DC link current feedback in electric and hybrid electric transmissions
- Comparative analysis of switched reluctance motor control algorithms
- Gas dynamics of stationary supersonic gas jets with inert particles exhausting into a medium with low pressure
- Mixed forms of free oscillations of a rectangular CFCF-plate
- Modeling of heat-hydrodynamic processes in evaporators of low-temperature systems with intrachannel boiling of refrigerants
- High performance modeling of the stress-strain state of thin-walled shell structures with the use of deep learning
- Validation of state machine specifications